package com.leetcode.array_matrix;

import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/10/15 17:16
 */
public class RandomIndex_398 {

    // 蓄水池采样算法
    static class Solution {

        private int[] nums;
        private Random random;

        public Solution(int[] nums) {
            this.nums = nums;
            random = new Random();
        }

        public int pick(int target) {
            int i = 1, res = -1;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == target && (res == -1 || random.nextInt(++i) == 0)) {
                    res = j;
                }
            }
            return res;
        }
    }

}
